﻿#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996)

#include "Sort.h"
#include "Stack.h"



void PrintArray(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void InsertSort(int* arr, int n)//直接插入排序
{
	for (int i = 0; i < n-1; i++)//注意这里的循环条件的控制，如果是小于n的话，后面的end+1会造成数组的越界访问。
	{
		int end = i;//end是最后一个有序数字的下标
		int tmp = arr[end + 1];
		
		while (end >= 0)//单趟的排序内容
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];//依次把前面的数据赋值到后面。
				end--;//所以这里的最后一个有序数字的下标需要不断的--，也就是向后挪动
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}//每一趟排序，都会让end+1位置之前的元素排成一个升序，等到把所有趟遍历完之后，数组元素绝对就是有序序列了。

void ShellSort(int* arr, int n)
{
	//int gap = 3;
	//for (int j = 0; j < gap; j++)
	//{
	//	for (int i = j; i < n - gap; i += gap)//当前这个程序只完成了一组的排序
	//	{
	//		int end = i;
	//		int tmp = arr[end + gap];
	//		while (end >= 0)
	//		{
	//			if (tmp < arr[end])
	//			{
	//				arr[end + gap] = arr[end];
	//				end -= gap;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//		arr[end + gap] = tmp;
	//	}
	//}
//这里要放到end+gap的位置，因为跳出while循环后，end多减了一次gap。也就是我们之前的思路，跳出while循环之后，将tmp放到end后面的位置
//只不过现在这个距离变为3了，所以就是放到end+3的位置


	//效率上没有变化，但代码更加简洁了
	//int gap = 3;
	//for (int i = 0; i < n - gap; i++)//这里的i++实现的是gap组并排
	//{
	//	int end = i;
	//	int tmp = arr[end + gap];
	//	while (end >= 0)
	//	{
	//		if (tmp < arr[end])
	//		{
	//			arr[end + gap] = arr[end];
	//			end -= gap;
	//		}
	//		else
	//		{
	//			break;
	//		}
	//	}
	//	arr[end + gap] = tmp;
	//}


	//gap > 1 预排序
	//gap == 1 间隔为1，完成对数组的最后一次排序，但这次排序所耗的时间会很短，效率很高。

	//进行多趟的预排序，然后再来进行最后一趟的直接插入排序。
	//通过预排序来减轻最后一次插入排序的负担
	int gap = n;
	while (gap > 1)
	{
		// gap = gap / 2;//这里最后肯定是1
		// gap = gap / 3;//这种方法是不行的，不能保证最后一次一定是1
		gap = gap / 3 + 1;//+1是为了保证这里最后一次一定是1，保证最后一次为直接插入排序
		//除3可以让预排次数更少一点。

		for (int i = 0; i < n - gap; i++)//这里的i++实现的是gap组并排
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
		PrintArray(arr, n);
	}

	//预排序：
	//1.gap越大，大的数可以更快到后面，小的数可以更快到前面。反过来，他也越不接近有序。太离散，整体性就不好了
	//2.gap越小，数据跳动越慢。但它也越接近有序。太整体，离散型也就差了，也就是数据跳动的越慢。
	//所以我们只要保证最后一次gap是1，也就可以保证数组是有序的了。
	
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* arr, int n)
{
	//直接选择排序就是不停的遍历数组，每次选出最小的数然后和首元素位置交换，下一次和首元素后面的位置进行交换，一个循环就可以搞定。

	//进阶的思想：遍历一遍，选出最大的和最小的，下一次选出次大和次小，每次放到数组的首尾位置，下次选出次首尾的位置。
	int begin = 0, end = n - 1;
	while (begin<end)//奇数个相遇，偶数个begin>end，所以我们的循环继续条件就是begin<end
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&arr[begin], &arr[mini]);//如果最大的数恰好在最左边，交换之后，最大数的下标已经变了，下面的交换也就不是最大数的交换了
		if (maxi == begin)//如果有重叠，我们就在这里修正一下
			maxi = mini;
		Swap(&arr[end], &arr[maxi]);//把最大的换到最右边
		//if (mini == end)//这里的修正完全是多余的，因为只要你修正一次，下面再进行交换时，是绝对不会出问题的。所以下面的交换是没必要的。
		//	mini = maxi;
		++begin;
		--end;
	}
	//选择排序的时间复杂度：O(N²)，每次遍历一遍数组，其实就是循环的次数变少了，但时间复杂度还是N²
	//选择排序和直接插入排序比较，谁更好？ -- 其实是插入排序更好
	//插入的适应性很强，对于有序，局部有序，都能效率提升

	//选择排序乱不成，看起来光鲜亮丽的，实际效率极低，要做人就做堆排序和希尔排序这样的人，要么就明面的好好学，要么就悄悄惊艳所有人。

	//选择排序为什么差劲呢？任何情况下都是N方，哪怕序列已经有序，或者接近有序依然时间复杂度是N方，人家插入排序一看序列有序，
	//只需要遍历一遍数组就完事了，一看没有元素小于前面的元素，遍历完就结束了，可不比你强太多了吗？

	//直接插入排序并不一定每次都是最坏情况，但选择排序每次都是最坏情况。肯定人家比你强啊！
	//直接插入排序和数据的分布也有一定的关系，分布较好，排序的时间也越短。
}

//void BubbleSort(int* arr, int n)
//{
//	//建议先写一趟的排序，然后再写整体的排序
//	for (int j = 0; j < n; j++)
//	{
//		for (int i = 0; i < n - 1 - j; i++)
//		{
//
//			if (arr[i] > arr[i + 1])
//			{
//				Swap(&arr[i], &arr[i + 1]);
//			}
//		}
//	}
//}

//稍微优化一下
void BubbleSort(int* arr, int n)
{
	//建议先写一趟的排序，然后再写整体的排序
	for (int j = 0; j < n; j++)
	{
		int exchange = 0;
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				Swap(&arr[i], &arr[i + 1]);
				exchange = 1;
			}
		}
		//一趟冒泡排序过程中，没有发生交换，说明已经有序了，不需要再处理
		//如果是部分有序，整体无序，那这个优化其实可有可无了就，起不到什么作用。还是干不过选择排序
		//但如果是有序的情况下的话，冒泡排序绝对能干的过选择了，因为它走一次就完全OK了，选择还来那里疯狂走呢，我冒泡早走完了都。
		if (exchange == 1)
			break;
	}
}

//1.hoare版本

	//单趟排序：左边的值比key要小，右边的值比key要大，key可以考虑选最左边的值或最右边的值
	//key是最左边就右边先走，是最右边就左边先走，待会儿解释
	//快排的单趟有两大意义：1.分割出左右区间，左区间比key小，右区间比key大2.key已经落到他正确的位置(排序后的最终位置)，key已经上岸了

	//左边做key，右边先走，保证相遇位置一定比key小，右边向左找小，左边向右找大。
	//右边做key，左边先走，保证相遇位置一定比key大

	//剩下的问题：
	//左区间有序，右区间有序，那么整体就OK了。递归处理剩下的问题即可

//证明：相遇无非两种情况
//1.相遇时，R停住，L遇到R，那么相遇位置就是R停住的位置，R停住的位置一定是要比key小的
//2.相遇时，L停住，R遇到L，那么相遇位置就是L停住的位置，L停住的位置一定是大于或等于key的，我们会将他和right进行交换
//  所以L位置的元素又会是比key小的了，所以只要让右边先走，那么相遇位置的元素一定是比key小的。
// 如果你让左边先走，很有可能相遇位置的元素是比key大的，还得再去找相遇位置前面的元素，很麻烦，费力不讨好。
//这两种情况无论哪种，相遇的位置就是比key小的位置。(默认key是最左边的数据)


//快排并没有要求你单趟怎么排，他只要求，你每次排完之后，key的左边都小于key，key的右边都大于key
//三数取中
//begin mid end
int GetMidIndex(int* arr, int begin, int end)//获取中间数的索引
{
	int mid = (begin + end) / 2;
	//三数取最大和三数取最小其实是很好取的，因为我们只需要比较两次就可以选出这两个最值
	//但三数取中间其实是很不好选的，因为我们需要两两比较数
	if (arr[begin] > arr[end])
	{
		if (arr[end] > arr[mid])
		{
			return end;
		}
		else if (arr[begin] < arr[mid])
		{
			return begin;
		}
		else
		{
			return mid;
		}
		
	}
	else// arr[begin] < arr[end]
	{
		if (arr[mid] < arr[begin])
		{
			return begin;
		}
		else if (arr[end] > arr[mid])
		{
			return mid;
		}
		else
		{
			return end;
		}

	}
}


//void QuickSort(int* arr, int begin,int end)
//{
//	if (begin >= end)//递归结束条件，当被分割的数组段仅剩一个元素或者没有元素的时候，递归停止。
//	{
//		return;
//	}
//
//
//	if ((end - begin + 1) < 15)//release版本优化太大了，导致小区间优化程度不够明显。
//	{
//		//小区间用直接插入替代，减少递归调用次数
//		InsertSort(arr + begin, end - begin + 1);//如果你传过去的是arr的话，那直接插入排序就会一直排前半部分了，不会排后半部分了。
//	}
//	else
//	{
//		int mid = GetMidIndex(arr, begin, end);
//		Swap(&arr[begin], &arr[mid]);
//		//这里其实就是为了保证我们所选到的最左边的数不是最大或最小的，要不然效率太低了，如果每次选到的都是靠中间的数的话，那递归的效率会
//		//很高，因为每层递归处理好的数据会以指数函数增长
//
//		int left = begin, right = end;
//		int key = left;
//		while (left < right)
//		{
//			//右边先走，找小
//			while (left < right && arr[right] >= arr[key])
//				//1.key右边所有值都大于key，有越界问题产生。
//				//2.左右两边如果都有跟key相等的值，那这个循环就会陷入死循环
//			{
//				--right;
//			}
//			//左边再走，找大
//			while (left < right && arr[left] <= arr[key])//逻辑与解决越界访问的问题，逻辑表达式加个等号防止死循环的产生
//			{
//				++left;
//			}
//			if (left > right)
//			{
//				break;
//			}
//			Swap(&arr[left], &arr[right]);
//		}
//
//
//		Swap(&arr[left], &arr[key]);
//		key = left;
//
//		//分割成了三个左区间……进行递归向下走
//		QuickSort(arr, begin, key - 1);
//		QuickSort(arr, key + 1, end);
//	}
//
//}
 
//小区间优化：快排分割到小区间时，用直接插入排序
//1.当我们递归分割的数据段过小的时候，其实已经没有必要使用递归子问题来解决了，再建立函数栈帧其实是白白的消耗空间，我们可以利用直接
//插入排序，这真的会给快排带来天翻地覆的改变，因为仅仅你少掉递归的最后一层，都可以减少掉原来函数开辟栈空间的个数的一半了，这优化
//的很牛逼了已经，在运行速度上又不知道要快了多少。
//2.所以如果我们将最后三层的递归解决子问题换成利用直接插入解决的话，我们可以省去大概%80的函数栈帧空间。多余的消耗其实就是直接插入
//  排序的消耗而已。

//如果面试官当面让我们写快排的时候，我们先写没有小区间优化和三数取中这样版本的，等到写完基础版本之后，再分别加上这两个优化，
//讲解给面试官听



//Hoare版本
int PartSort1(int* arr, int begin, int end)
{
	int mid = GetMidIndex(arr, begin, end);
	Swap(&arr[begin], &arr[mid]);
	//这里其实就是为了保证我们所选到的最左边的数不是最大或最小的，要不然效率太低了，如果每次选到的都是靠中间的数的话，那递归的效率会
	//很高，因为每层递归处理好的数据会以指数函数增长

	int left = begin, right = end;
	int key = left;
	while (left < right)
	{
		//右边先走，找小
		while (left < right && arr[right] >= arr[key])
			//1.key右边所有值都大于key，有越界问题产生。
			//2.左右两边如果都有跟key相等的值，那这个循环就会陷入死循环
		{
			--right;
		}
		//左边再走，找大
		while (left < right && arr[left] <= arr[key])//逻辑与解决越界访问的问题，逻辑表达式加个等号防止死循环的产生
		{
			++left;
		}
		if (left > right)
		{
			break;
		}
		Swap(&arr[left], &arr[right]);
	}

	Swap(&arr[left], &arr[key]);
	key = left;
	return key;
}

//  挖坑法
int PartSort2(int* arr, int begin, int end)
{
	int mid = GetMidIndex(arr, begin, end);
	Swap(&arr[begin], &arr[mid]);
	//这里其实就是为了保证我们所选到的最左边的数不是最大或最小的，要不然效率太低了，如果每次选到的都是靠中间的数的话，那递归的效率会
	//很高，因为每层递归处理好的数据会以指数函数增长

	int left = begin, right = end;
	int key = arr[left];
	int hole = left;//第一个坑位置的下标
	while (left < right)
	{
		//右边找小，填到左边的坑里面
		while (left < right && arr[right] >= key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] <= key)
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	//left和right相遇的时候，一定是到达坑位了，我们把坑位的值换成key，key就去到他应该去到的位置了
	arr[hole] = key;
	return hole;//最后坑位hole的坐标就是，key最后应该落的位置。
}
int PartSort3(int* arr, int begin, int end)//推荐使用前后指针这样的方法来实现快速排序，hoare和挖坑法也要掌握
{
	//加一个三数取中，让单趟递归稍微优化一下
	int mid = GetMidIndex(arr, begin, end);
	Swap(&arr[begin], &arr[mid]);
	/*1.cur找比key小的值
	2.++prev，然后交换prev和cur的值
	3.prev位置的值是始终要比key小的，也有可能prev没有动，呆在和key相同的位置。*/

	int key = begin;
	int prev = begin, cur = begin + 1;
	while (cur <= end)//end是最后一个元素的下标，这里用的是闭区间的形式，所以我们要带一个等号。
	{
		//找到比key小的值时，跟++prev位置交换，小的到前面，大的到后面
		if (arr[cur] < arr[key] && ++prev!=cur)
		//第一个元素就小于key时，cur就停下来了，防止cur和prev位置重复的时候还进行交换，这时交换没必要。
		{
			Swap(&arr[prev], &arr[cur]);
		}
		++cur;//cur一直向后走，遇到比key小的值的时候，cur要停下来和++prev位置元素进行交换
	}
	Swap(&arr[prev], &arr[key]);//prev最后停下位置的元素一定是比key小的，我们可以放心的交换prev和key位置的元素。
	key = prev;
	return key;

}
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)//递归结束条件，当被分割的数组段仅剩一个元素或者没有元素的时候，递归停止。
	{
		return;
	}

	if ((end - begin + 1) < 15)//release版本优化太大了，导致小区间优化程度不够明显。
	{
		//小区间用直接插入替代，减少递归调用次数
		InsertSort(arr + begin, end - begin + 1);//如果你传过去的是arr的话，那直接插入排序就会一直排前半部分了，不会排后半部分了。
	}
	else
	{
		int key = PartSort1(arr, begin, end); 

		//分割成了三个左区间……进行递归向下走
		QuickSort(arr, begin, key - 1);
		QuickSort(arr, key + 1, end);
	}
}

void QuickSortPlus(int* arr, int begin, int end)//这个版本有些延续了之前的前后指针版本的想法，
{
	int mid = GetMidIndex(arr, begin, end);
	Swap(&arr[begin], &arr[mid]);
	
	int left = begin, right = end;
	int key = arr[left];
	int cur = begin + 1;
	while (cur <= right)//当cur与right错过的时候，这时大于key小于key等于key的数据就都到他们各自的位置了
	{
		if (arr[cur] < key)
		{
			Swap(&arr[cur], &arr[left]);
			cur++;
			left++;
		}
		else if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right]);
			right--;
		}
		else  //arr[cur] == key
		{
			cur++;
		}//循环结束之后，left和right之间的数字就是和key相等的数字
	}

	// [begin,left-1] [left,right] [right+1,end] 分成了这样的三段区间

	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, end);	
}


//非递归版本快排
void QuickSortNonR(int* arr, int begin, int end)//我们应该具有将递归改为非递归的能力
{
	//普通的递归改非递归，直接改为循环即可。
	//复杂的递归改非递归，一般需要借助栈这个数据结构

	//每次压栈区间的左右下标，模拟递归的实现
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))//如果栈不为空的话，就取栈中的区间出来，对区间里面的内容进行前后指针版的快排，这样就可以确定一个数的数据
	{
		//取一个区间出来，单趟排序之后，就可以确定好key的位置了
		//如果我们一次只入栈一个区间的话，那样肯定是不行的，因为key另一边的区间你没有管，所以我们入栈一次就得入栈两个区间

		//如果想要先排左，再排右的话，那入栈的顺序肯定要反过来，先入右再入左。
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int key = PartSort3(arr, left, right);
		//  [left,key-1] key [key+1,right]

		if (key + 1 < right)//key+1==right时，区间内只有一个数，那就无需入栈了，因为这个数已经落到它应该在的位置了
		{
			StackPush(&st, key + 1);
			StackPush(&st, right);
		}

		if (left < key - 1)//这个条件判断相当于递归的返回值，递归遇到一个值的时候，就return了，我们这里是就不让他入栈了，停止单趟排序
		{
			StackPush(&st, left);
			StackPush(&st, key - 1);
		}
	}
	//深度用栈，广度用队列
	StackDestroy(&st);
}

//归并排序
//如果左半区间有序，右半区间有序，那我们直接归并即可，两个区间依次比较，取较小的元素尾插到新的数组里面。
//快排可以认为是前序遍历，先处理根，在处理左右，归并可以认为是后续，若左右无序，那就递归向下走，分成左右子树，
//等到左边有序，右边有序，此时就要归并了，层层的返回，等到最大的左右区间都有序后，我们一归并，这样就可以得到完整的升序序列了。

//归并还是有点类似于快排的，都是分割子区间到最小，然后开始返回，返回到最高层，递归结束，归并序列完成

void _MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin>=end)//应该是不存在区间错过的情况的
	{
		return;
	}
	int mid = (begin + end) / 2;
	// [begin,mid] [mid+1,end]  --  递归让子区间有序
	//如果左右区间没有序，我们就向下递归，让他有序
	_MergeSort(arr, begin, mid, tmp);
	_MergeSort(arr, mid + 1, end, tmp);

	//左右区间有序之后，我们对两段区间进行归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;//这样命名的方式会让我们后面的归并不会影响前面。
	int i = begin;//这里的i不可以定义成0，因为你下面有可能递归的是最大的右区间，
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	//到这里肯定还有一个区间是空的，我们只要将剩下的区间尾插到tmp数组里面即可
	//下面这两个条件肯定有一个是满足的，我们就不用if条件来判断了，直接写两个循环，哪个符合，进哪个循环就可以了。我们什么都不用管。
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
	//拷贝字节数应该是要加1的，因为end是闭区间，字节数是要+1的。而且，假设你有两个数，你想拷贝两个值，拷贝的个数肯定是两个数做差
	//然后加1。
}
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	//在归并排序本身这个函数里面我们肯定是不能递归的，我们malloc空间肯定是只malloc一次，所以需要额外定义一个子函数来完成递归的任务。
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);//防止内存泄露
	tmp = NULL;
}



//入栈左右两个子区间，我们先取出一个子区间进行处理，处理之后这个区间就没了，那我们就算处理好另一个子区间也没用了，无法进行两个子区间
//的归并了，所以无论是栈还是队列，只要你想进行归并向下处理，那你肯定得pop掉之前的区间，之前的大区间都pop掉了，那你咋拿两个大区间进行
//归并排序呢？

//所以对于这样后序的情况的话，栈和队列这样的结构，并不能很好的解决我们的非递归所面临的问题，但前序还是可以借助栈和队列来处理的。因为
//前序提前就把根处理好了。

//因为我们可以确定分割的最小区间是一个数，然后一个数和一个数归变成两个数，两个数和两个数归变成四个数，所以我们不需要额外的数据结构
//来进行非递归，我们直接控制就好了。
//写法一：
void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			//这里面要实现两个组数据的归并
			// [begin1,end1][begin2,end2] 归并

			int begin1 = i, end1 = i + rangeN - 1;//归并区间1
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			int j = i;
			//end1 begin2 end2越界
			if (end1 >= n)
			{
				//修正区间  ->拷贝数据可以整体拷贝，也可以归并每组拷贝，因为无论哪种，tmp中的数据不会存在随机值的情况
				end1 = n - 1;
				//让第一个区间修正成一个正确的区间
				//将第二个区间修正成一个不存在的区间。
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				//修正成不存在的区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])//加个等号，遇到相同数字，取前一个，保证算法稳定性
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			//强烈推荐归并一点，我们就往原数组拷贝回去一点，别一次性就全都拷贝回去

			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
			//拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
		}

		//也可以整体归并完了，再统一将tmp数组拷贝回arr里。
		//memcpy(arr, tmp, sizeof(int) * n);//这就是整体拷贝。

		rangeN *= 2;
	}
	free(tmp);//防止内存泄露
	tmp = NULL;
}
//rangeN是归并的每组的数据个数，然后我们两两为一组，进行归并。
//然后我们每次让range扩大二倍，最后的两组进行归并，结束后，我们就可以得到一个完整的归并序列了。

//先前有问题的逻辑：
//但到了10个测试数据的时候，由于他不是2的n次方个，无法被两两分成一个归并组，出现越界访问。例如rangeN==2时，两两分为一组，肯定有两个
//数据被落下，无法和其他数据凑成一个归并组。除了这样的情况之外，还有很多其他的越界情况，我们需要一一分析


//如果你是修正了区间，以防越界访问的话，那既可以整体拷贝，也可以部分拷贝。
//如果你遇到越界访问，选择跳出归并循环的话，那就不可以整体拷贝，只能部分拷贝。

//写法二：
//void MergeSortNonR(int* arr, int n)//栈和队列进行非递归都非常不好搞
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//
//	//rangeN代表归并的每组数据个数，从1开始，因为一个数认为是有序的，可以直接进行归并。
//	int rangeN = 1;
//	while (rangeN < n)
//	{
//		for (int i = 0; i < n; i += 2 * rangeN)
//		{
//			//这里面要实现两个组数据的归并
//			// [begin1,end1][begin2,end2] 归并
//
//			int begin1 = i, end1 = i + rangeN - 1;//归并区间1
//			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;//归并区间2，加上2倍的rangeN之后，就跳到下一组了，-1正好就是本组的最后一个元素
//			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
//			int j = i;
//			//end1 begin2 end2越界
//			if (end1 >= n)
//			{
//				//如果你不修正直接走break，那你是不能整体拷贝的，因为tmp中有一部分值会是随机值，
//				break;
//			}
//			else if (begin2 >= n)
//			{
//				break;
//			}
//			else if (end2 >= n)
//			{
//				end2 = n - 1;//对end2进行修正
//			}
//			while (begin1 <= end1 && begin2 <= end2)
//			{
//				if (arr[begin1] <= arr[begin2])//加个等号，保证归并排序是稳定的，遇到相同数字，我们取前一个
//				{
//					tmp[j++] = arr[begin1++];
//				}
//				else
//				{
//					tmp[j++] = arr[begin2++];
//				}
//			}
//
//			while (begin1 <= end1)
//			{
//				tmp[j++] = arr[begin1++];
//			}
//			while (begin2 <= end2)
//			{
//				tmp[j++] = arr[begin2++];
//			}
//			
//			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
//			//拷贝的个数是2*rangeN是不可以的，因为数据有可能不是恰好分成整数个组，我们有时可能只拷贝一个数据。
//		}
//		rangeN *= 2;
//	}
//	free(tmp);//防止内存泄露
//	tmp = NULL;
//}

void CountSort(int* arr, int n)
{
	int max = arr[0], min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if(arr[i]<min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;//[0,2]左闭右闭的情况下，数据的个数一定是要+1的。如果是开区间自然不用，(0,2]数据个数为2。
	//统计次数
	int* countA = (int*)calloc(range, sizeof(int));
	if (countA == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < n; i++)//再次遍历arr数组，统计其中数据出现的次数
	{
		countA[arr[i] - min]++;//这里就统计出数据出现的次数了
	}
	//遍历统计次数的数组，对原数组进行计数排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)//n--走n次，--n走n-1次。
		{
			arr[j++] = i + min;
			//这里又犯了一个严重的错误，利用了循环变量i，可千万不敢用循环变量i啊，要不然循环的情况就被你改了，代码又出问题了，你妹的。
		}
	}
	free(countA);
	countA = NULL;
}
//时间复杂度：O(N+range)，虽然有两层循环嵌套在一起，但不是×的关系，其实是加的关系。
//空间复杂度：O(range)
//适合数据范围集中，也就是range小
//只适合整型数据的排序，不适合浮点数、字符串等类型。

//如果数据较为集中的话，计数排序还是非常牛逼的，因为N大于range的话，我们的时间复杂度就是O(N)，老天爷，这性能不妥妥的很强么。







































